#pragma once
#include <iostream>
#include <vector>
using namespace std;

namespace LinkHash
{
    template<class T>
    struct Hash
    {
        size_t operator()(const T& key) { return key; }
    };

    template<>
    struct Hash<string> {
        size_t operator()(const string& key) {
            int ret = 0;
            for (auto ch : key) {
                ret += ch;
                ret *= 31;
            }
            return ret;
        }
    };


    template<class K, class V>
    struct HashNode
    {
        HashNode(const pair<K, V>& kv)
            :_kv(kv)
            , _next(nullptr)
        {}

        pair<K, V> _kv;
        HashNode<K, V>* _next;
    };

    template<class K, class V, class HashFunc = Hash<K>>
    class HashTable
    {
        typedef HashNode<K, V> Node;
    public:
        bool Insert(const pair<K, V>& kv);
        Node* Find(const K& key);
        bool Erase(const K& key);
    private:
        vector<Node*> _tables;
        size_t _n = 0;
    };

    template<class K, class V, class Hash>
    bool HashTable<K, V, Hash>::Insert(const pair<K, V>& kv)
    {
        if (!_tables.empty() && Find(kv.first))
            return false;
        Hash hs;
        if (_n >= _tables.size())
        {
            //扩容
            size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
            vector<Node*> newTables;
            newTables.resize(newSize);
            for (size_t i = 0; i < _tables.size(); i++)
            {
                Node* cur = _tables[i];
                while (cur)
                {
                    Node* next = cur->_next;
                    size_t index = hs(cur->_kv.first) % _tables.size();
                    cur->_next = newTables[index];
                    newTables[index] = cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newTables);
        }
        size_t index = hs(kv.first) % _tables.size();
        Node* NewNode = new Node(kv);
        NewNode->_next = _tables[index];
        _tables[index] = NewNode;
        ++_n;
        return true;
    }

    template<class K, class V, class Hash>
    HashNode<K, V>* HashTable<K, V, Hash>::Find(const K& key)
    {
        if (_tables.empty())
            return nullptr;
        Hash hs;
        size_t index = hs(key) % _tables.size();
        Node* start = _tables[index];
        while (start && start->_kv.first != key)
        {
            start = start->_next;
        }
        return start;
    }

    template<class K, class V, class Hash>
    bool HashTable<K, V, Hash>::Erase(const K& key)
    {
      Hash hs;
      size_t index = hs(key) % _tables.size();
      Node* cur = _tables[index];
      Node* prev = nullptr;
      while (cur && cur->_kv.first != key)
      {
        prev = cur;
        cur = cur->_next;
      }
      if (cur == nullptr)
        return false;
      else if (prev == nullptr)
      {
        Node* next = cur->_next;
        _tables[index] = next;
        delete cur;
        cur = nullptr;
        return true;
      }
      else 
      {
        prev->_next = cur->_next;
        delete cur;
        cur = nullptr;
        return true;
      }
    }
    void TestHashTable()
    {
        HashTable<int, int> ht;
        int arr[] = { 1, 11, 21, 31, 5, 6, 7, 8, 9,10, 44 };
        for (auto e : arr)
        {
            ht.Insert(make_pair(e, e));
        }
        cout << endl;
    }



















}

